This invention is generally related to the design and manufacture of Very Large Scale Integrated circuits, and more particularly to a method for extracting parasitic capacitances from interconnect wiring thereof.
The method of tetrahedralization for 3-D objects has been studied extensively for a variety of engineering applications for a long time. With the advent of Computer Aided Design Tools (CAD) in both civil/mechanical designs automation and electronic design automation have created renewed interest in the development of efficient tetrahedralization methods. One limitation of the implementation of such methods using digital computers is the limitation imposed by the finite word sizes for both fixed point and floating point computations. Long numbers are either truncated or rounded off to fit into a bounded word size. As a result, the geometric and topological properties of the tetrahedralization are no longer satisfied. Tetrahedralization has been the subject of several patents.
By way of example:
U.S. Pat. No. 5,553,206 to Meshkat describes an algorithm to generate a mesh representation of an arbitrarily shaped object for applications such as finite element analysis. The method includes identifying elements of a mesh, such as a tetrahedral mesh, which are suitable, based on predetermined criteria, for merging into one of a predetermined set of target elements.
U.S. Pat. No. 6,133,921 to Turkiyyah et al. describes the construction of shape skeletons of 3-D objects using generalized Voronoi diagrams, refining it to reduce discretization errors.
U.S. Pat. No. 5,774,696 to Akiyama describes a finite difference method for refining a mesh to better follow the surface boundary.
An intersection between a substance boundary and triangles/tetrahedra meshes which satisfy the conditions of a Delaunay partition are eliminated.
U.S. Pat. No. 5,553,009 to Meshkat et al. describes a method of subdividing a curved solid into simple “cells”, and arbitrarily shaped objects into a collection of geometric elements (“cells”) having predefined simple topologies to facilitate further subdivisions into tetrahedra. This approach is well suited for other applications, such as finite element calculations.
None of the aforementioned patents address the round-off problem in tetrahedralization or numerical problems due to rounding errors.
Additionally, there have been several papers available in the open literature addressing this type of problems, some of which have attempted to handle round-off problems in the implementation of geometric algorithms.
Some researchers advocate computations in the exact precision domain, such as S. Fortune and V. Milenkovic, “Numerical stability of Algorithms for Line Arrangement Problems”, ACM Symposium of Computational Geometry Proceedings, 1991, and C. Burnickel, K. Mehlhorn and S. Schirra , “On Degeneracy in Geometric Computations”, Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms, pp. 16–23, 1994. The proposed methods suffer serious drawbacks in that they become very slow when the size of computations increases, ending in a process that becomes soon unmanageable.
V. J. Milenkovic, in the paper “Verifiable Implementations of Robust Geometric Algorithms using Finite Precision Arithmetic”, Carnegie Mellon University Technical Report CMU-CS-88-168, 1988, describes a method for intersecting lines in two dimensions. However, this approach introduces additional vertices and, hence, is more expensive.
D. H. Greene and F. F. Yao, in a paper “Finite Resolution Computational Geometry”, published in the Proceedings of the Twenty-seventh Annual IEEE-FOCS Conference, pp.143–152, 1986, describe a method for intersecting lines in two dimensions. Again, this method is difficult to implement and is very slow. Further, this approach is limited to problems that do not involve any geometric decision making.
The limited use of diagonal wiring in VLSI chips has shown itself capable of improving chip performance by reducing net delay, a major component thereof being found to reside in the capacitive coupling between nets. An effective approach to handling wiring of all orientations is known as the finite element method. Practitioners of the art will recognize that the finite element method is best suited for modeling multiple dielectrics.
A tetrahedra mesh is recommended for 3-D finite element discretization. In the above application, a long wire is subdivided into small tetrahedra covering as closely as possible the volume and the surface of the wiring. In addition to that the spacing between different wires is also divided into tetrahedra for the finite-element analysis of the parasitic capacitances. In this manner, a problem in the continuous domain can be solved by techniques using discretized domains. Since the tetrahedralization of the continuous object is an approximation of the actual object, it is crucial that the fidelity of the approximation be high. In order to make a close approximation many tetrahedralization algorithms generate narrow and thin tetrahedrons.
An example of tetrahedralization is illustrated in FIG. 1. Shown therein are two wires crossing each other and the 3-D mesh generated between them for a finite element analysis of parasitic capacitances.
For the correctness of the extraction routine that uses tetrahedralization as a basis, it is essential that the exactness of the topology of the tetrahedrons be maintained. A topologically correct tetrahedralization without any spurious intersections among its components is known as a simplicial complex in three dimensions.
The topological correctness of the simplicial complex helps to establish a relationship between the continuous domain of the real object and its discretized tetrahedralization approximation. Without this consistency, analyses based on the tetrahedralization may give ambiguous results.
Many extraction algorithms incorporating the tetrahedralization algorithms therein are susceptible to round-off errors emanating from floating point computations. Errors are caused by the finite byte size used in a computer to store floating-point or fixed-point numbers. As a result of the finite byte size, numbers are truncated or rounded off at the end thereof. These truncations tend to accumulate over the complete set of computations, translating in the loss of precision of the numbers. By way of example, it is difficult to guarantee that two tetrahedra (adjacent or not) will not display a volume intersection because of numerical errors. Often, due to floating point errors, a tetrahedron or a surface thereof may lead to a topological inversion making it difficult to define the enclosed volume unambiguously. The problem of numerical imprecision is accentuated in 3-D tetrahedralization problems by the presence of very long and thin tetrahedra and acuteness of the component triangles.
FIG. 2 shows what typically happens when the space between the two wires becomes too small, wherein there is a tendency to generate sliver or small tetrahedra that are susceptible to numerical imprecision due to rounding errors.
For a typical simple tetrahedral mesh of VLSI layout, 2-dimensional shape coordinates are projected onto the x-y plane and 3-D prisms are extruded to fill the space between conductor shapes. Then prisms are split into tetrahedra. Shapes wherein the projections that come in close proximity without exactly meeting can result in a poor mesh quality. Thus, there is a need for a methodology that guarantees all the properties of a simplicial complex to be maintained in any tetrahedralization.
FIG. 3 illustrates the case of a 2-dimensional wiring consisting of two wires crossing each other diagonally. Shape projections that barely overlap one another, or shape projections that just miss touching result in flat tetrahedra. In the former case, the spacing between the two wires becomes very small, generating sliver tetrahedral in the region. Sliver tetrahedra are potentially problematic due to round-off errors. Moreover, depending on the direction of the overlap there may be little or no difference in one of their coordinates, leading to the formation of a flat tetrahedral. This effect is illustrated in FIG. 4 depicting 3-D top-down and isometric views of a typical VLSI layout where diagonal wiring is allowed.
As stated previously, when shape projections barely overlap one another as, for instance, near “A”, the result is a sliver tetrahedra. Where shape projections just miss touching, e.g., near “B”, the result is a nearly flat tetrahedra. Both slivers and nearly flat tetrahedra are poor mesh elements. Using the 3-D proximity based rounding method, environment A changes to A″, with the three points near A merging into one, eliminating the sliver tetrahedra. Environment B changes to B″, which eliminates the nearly flat tetrahedron and results in four triangular faces. In both cases, the 3-D proximity based rounding method improves the mesh.
FIG. 5 shows a typical case of parasitic capacitance extraction within which a tetrahedralization routine is used. Given an integrated circuit layout 501, regions of wire interactions 502 are first computed. These regions are used for computing tetrahedralization 503, and the result of this tetrahedralization is then employed for finite-element analysis 504. The output of the finite element analysis is instrumental in solving Maxwell's equation 505, and more specifically, for computing and extracting parasitic capacitances 506.
FIG. 6 shows the basic assumptions and a practical application of a tetrahedralization algorithm (shown in FIG. 5) within which the current state of the art is implemented. A polyhedron is first defined by its face edges and vertices 601. The input polyhedron for the case of parasitic capacitance extraction will become one of the regions of wire interactions. The input numerical values for vertices faces and edge equations for the input polyhedron are specified using integers or in terms of some bounded precision. Tetrahedralization is computed using a higher precision than the input precision 602, e.g., double-precision numbers, if the input was specified in integers. However, at the same time, these higher precision numbers are rounded to the closest integer points 603. Finally, the result represented with integer numerical values is generated at the output 604.
FIG. 7 is a current state of the art flow chart. The input of the program is a set of 3-D shapes 702 given in integer coordinates. The methodology then computes the tetrahedralization using double precision 703. The vertices and numerical coefficients of faces and edges of a tetrahedron defined using double precision are referred to as being unrounded, since they are eventually “rounded” to the closest integer grid point. Next, the method rounds the coordinates back to single precision integers 704 and outputs the results 705. The problem with rounding is described in the following two examples in conjunction with corresponding FIGS. 8 and 9. For the case described hereinafter, rounding causes spurious,intersection or topological inversion resulting in volume conflicts (i.e., a positive volume tetrahedron being transformed into a negative volume tetrahedron).
FIG. 8 shows a current state of the art process illustrating the methodology described in FIG. 7. Two tetrahedra 801 and 802 are shown sharing a common vertex 803. When the vertex 803 is rounded to its closest integer-grid point 806, tetrahedron 801 is transformed into tetrahedron 804, and tetrahedron 802 into tetrahedron 805. Tetrahedra 804 and 805 intersect each other, violating topological consistencies. For correct computation of Maxwell's equation, it is important that no two tetrahedra intersect. The above rounding violates this assumption.
FIG. 9 illustrates a case that was created by the prior art flow chart depicted in FIG. 7. Shown therein are two tetrahedra 901 and 902 sharing a common plane “C”. When vertex 903 belonging to tetrahedron 902 is approximated to its closest integer-grid point 906, tetrahedron 901 is transformed into tetrahedron 904, while tetrahedron 902 is transformed into tetrahedron 905. Both 904 and 905 intersections violate topological consistencies with the volume enclosed by 905 becoming a negative volume that is partly enclosed by tetrahedron 904, creating a topological inversion. For correct computation of Maxwell's equation, it is important that the volume enclosed by each tetrahedron remain positive. The rounding in the present example violates this basic assumption.
FIG. 10 illustrates a finite precision computer to implement the present invention. It consists of a Central Processing Unit 1001, an Input-Output (IO) unit 1002, a communication interface 1003 and a Memory 1004. Data consists of a finite number of bytes 1006 handled by bus 1005. As a result, any number not sufficiently long to be represented by a word size is either truncated or rounded off.
Therefore, the longer the size of the word, the more precise the representation of the object in the computer. This truncation does not guarantee satisfaction of topological properties listed above, and further it has a negative impact on downstream applications.
When the current state of the art tetrahedralization algorithm illustrated in FIG. 7 is implemented within a digital computer as shown, e.g., in FIG. 10, spurious intersections or volume inversions are obtained, similar to the shapes illustrated in FIGS. 8 and 9, respectively.